#include <iostream>
#include <vector>

using namespace std;
// 509. 斐波那契数

// 记忆化搜索
class Solution {
public:
    int fib(int n) {
        vector<int> memo(n+1,-1);
        memo[0] = 0;
        memo[1] = 1;
        return dfs(n, memo);
    }

private:
    int dfs(int n, vector<int>& memo) {
        if( n <= 1) return n;
        if(memo[n] >= 0) return memo[n];
        return memo[n] = dfs(n-1, memo) + dfs(n-2,memo);
    }
};

int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
